package com.shiguiwu.springmybatis.algorithm.linkedlist;


import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * @description: 单链表
 * @author: stone
 * @date: Created by 2021/3/3 23:10
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.linkedlist
 */
public class SingleLinkedList {


    private HeroNode head;

    public SingleLinkedList() {
        this.head = new HeroNode(0, "水浒传", "");
    }

    public void add(HeroNode node) {
        HeroNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
    }

    /**
     * 添加顺序节点。。。。。
     * @param node
     */
    public void addBySort(HeroNode node) {
        HeroNode temp = head;
        while (temp.next != null ) {
            if (temp.next.no > node.no) {
                HeroNode t = temp.next;
                temp.next = node;
                node.next = t;
                return;
            }
            temp = temp.next;

        }
        temp.next = node;
    }

    public void update(HeroNode newNode) {
        HeroNode temp = head.next;
        this.checkNode(temp);
        boolean flag = false;
//        while (temp != null ) {
//            if (temp.no == newNode.no) {
//                temp = newNode;
//            }
//            temp = temp.next;
//        }

        while (true) {
            if (temp == null) {
                break;//链表遍历完，未找到
            }
            if (temp.no == newNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            temp.name = newNode.name;
            temp.nickname = newNode.nickname;
        }
        else {
            System.out.println("未找到修改节点~~~" + newNode);
        }
    }

    public void delete(int no) {
        HeroNode temp = head;
        this.checkNode(temp.next);
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;//链表遍历完，未找到
            }
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;//后移，遍历
        }

        if (flag) {
            temp.next = temp.next.next;
        }
        else {
            System.out.println("未找到删除节点~~~" + no);
        }


    }


    public void deleteRepeat(HeroNode node) {

        this.checkNode(node);
        Set<Integer> set = new HashSet<>();

        HeroNode temp = node;
        set.add(temp.no);
        while (temp.next != null) {
            if (!set.add(temp.next.no)) {
                temp.next = temp.next.next;
                temp = temp.next.next;//后移两位
            }
            else  {
                temp = temp.next;//后移，遍历
            }

        }



    }

    /**
     * 求有效节点的个数
     * 不包括头结点
     * @return
     */
    public int length() {
        int length = 0;
        HeroNode temp = head.next;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        System.out.println("节点的大小为：" + length);
        return length;
    }

    /**
     * 查询倒数第k个节点
     * @param k
     * @return
     */
    public HeroNode findLastIndexNode(int k) {
        HeroNode temp = head.next;
        this.checkNode(temp);
        int length = this.length();
        if (k <= 0 || k > length) {
            return null;
        }

        for (int i = 0; i < length - k; i++) {
            temp = temp.next;
        }
        System.out.println("查找到的倒数第k个节点：" + temp);
        return temp;
    }

    /**
     * 链表反转。。。。。
     * @return
     */
    public HeroNode reverse() {
        HeroNode revs = new HeroNode(-1, "", "");

        HeroNode temp = head.next;
        if (temp == null || temp.next == null) {
            return head;
        }

        //变量保存当前节点的下一个节点，用来遍历
        HeroNode next = null;
        while (temp != null) {
            next = temp.next;
            //todo 头插法的精髓所在，在头的下一个赋值给新插入的节点的下一个
            temp.next = revs.next;
            //头的下一个变了当前要插入的节点
            revs.next = temp;
            //继续遍历
            temp = next;

            //疑惑，引用重新赋值，并不会改变其他已经赋值的对象

        }
        //最后连接头部信息
        head.next = revs.next;
        return head;
    }

    /**
     * 打印链表
     */
    public void print() {
        HeroNode temp = head.next;
        this.checkNode(temp);
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }


    }

    /**
     * 逆序打印，不改变链表的结构
     * 思路是采用stack
     */
    public void reversePrint() {
        HeroNode temp = head.next;
        this.checkNode(temp);
        Stack<HeroNode> stack = new Stack<>();
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }

        while (!stack.empty()) {
            System.out.println(stack.pop());
        }

    }

    public void checkNode(HeroNode temp) {
        if (temp == null) {
            System.out.println("链表为空，不支持操作~~");
            throw new UnsupportedOperationException("链表为空，不支持操作~~");
        }
    }



    //水浒英雄
    public static class HeroNode {
        //链表的顺序
        private int no;

        //名称
        private String name;

        //昵称
        private String nickname;

        //下一个节点
        private HeroNode next;

        public HeroNode(int no, String name, String nickname) {
            this.no = no;
            this.name = name;
            this.nickname = nickname;
        }

        @Override
        public String toString() {
            return "HeroNode{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    ", nickname='" + nickname + '\'' +
                    '}';
        }
    }
}
